<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>拼图游戏——综述 | 软工个人项目——拼图游戏</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="零、综述为了更加清晰地说明和展示程序的详细设计和工作内容，本次的课程博客共由六篇博客文章组成。  拼图游戏———游戏介绍 拼图游戏———综述 程序设计——拼图文件生成 程序设计——问题求解 运行展示——命令台 运行展示——GUI  一、个人PSP表格   PSP2.1 Personal Software Process Stages 预估耗时（分钟） 实际耗时（分钟）    Planning 计划">
<meta property="og:type" content="article">
<meta property="og:title" content="拼图游戏——综述">
<meta property="og:url" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/index.html">
<meta property="og:site_name" content="软工个人项目——拼图游戏">
<meta property="og:description" content="零、综述为了更加清晰地说明和展示程序的详细设计和工作内容，本次的课程博客共由六篇博客文章组成。  拼图游戏———游戏介绍 拼图游戏———综述 程序设计——拼图文件生成 程序设计——问题求解 运行展示——命令台 运行展示——GUI  一、个人PSP表格   PSP2.1 Personal Software Process Stages 预估耗时（分钟） 实际耗时（分钟）    Planning 计划">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/1.png">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/2.png">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/14.png">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/15.png">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/4.bmp">
<meta property="og:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/6.png">
<meta property="article:published_time" content="2020-12-28T10:43:45.000Z">
<meta property="article:modified_time" content="2021-02-07T14:32:12.880Z">
<meta property="article:author" content="王欣哲 1120182955">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/1.png">
  
    <link rel="alternate" href="/hexo/atom.xml" title="软工个人项目——拼图游戏" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/hexo/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/hexo/css/style.css">

  
    
<link rel="stylesheet" href="/hexo/fancybox/jquery.fancybox.min.css">

  
<meta name="generator" content="Hexo 5.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/hexo/" id="logo">软工个人项目——拼图游戏</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/hexo/" id="subtitle">王欣哲 1120182955</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/hexo/">Home</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/hexo/atom.xml" title="RSS 订阅"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="搜索"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="搜索"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://BIT-WXZ.gitee.io/hexo"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-拼图游戏——综述" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/" class="article-date">
  <time class="dt-published" datetime="2020-12-28T10:43:45.000Z" itemprop="datePublished">2020-12-28</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      拼图游戏——综述
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h2 id="零、综述"><a href="#零、综述" class="headerlink" title="零、综述"></a>零、综述</h2><p>为了更加清晰地说明和展示程序的详细设计和工作内容，本次的课程博客共由六篇博客文章组成。</p>
<ol>
<li><strong><a href="/hexo/2020/12/26/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E6%B8%B8%E6%88%8F%E4%BB%8B%E7%BB%8D/">拼图游戏———游戏介绍</a></strong></li>
<li><strong><a href="/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/">拼图游戏———综述</a></strong></li>
<li><strong><a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90/">程序设计——拼图文件生成</a></strong></li>
<li><strong><a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a></strong></li>
<li><strong><a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94%E5%91%BD%E4%BB%A4%E5%8F%B0/">运行展示——命令台</a></strong></li>
<li><strong><a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94GUI/">运行展示——GUI</a></strong></li>
</ol>
<h2 id="一、个人PSP表格"><a href="#一、个人PSP表格" class="headerlink" title="一、个人PSP表格"></a>一、个人PSP表格</h2><table>
<thead>
<tr>
<th align="center">PSP2.1</th>
<th align="center">Personal Software Process Stages</th>
<th align="center">预估耗时（分钟）</th>
<th align="center">实际耗时（分钟）</th>
</tr>
</thead>
<tbody><tr>
<td align="center">Planning</td>
<td align="center">计划</td>
<td align="center">30</td>
<td align="center">20</td>
</tr>
<tr>
<td align="center">· Estimate</td>
<td align="center">· 估计这个任务需要多少时间</td>
<td align="center">30</td>
<td align="center">20</td>
</tr>
<tr>
<td align="center">Development</td>
<td align="center">开发</td>
<td align="center">1560</td>
<td align="center">1885</td>
</tr>
<tr>
<td align="center">· Analysis</td>
<td align="center">· 需求分析 (包括学习新技术)</td>
<td align="center">180</td>
<td align="center">120</td>
</tr>
<tr>
<td align="center">· Design Spec</td>
<td align="center">· 生成设计文档</td>
<td align="center">30</td>
<td align="center">40</td>
</tr>
<tr>
<td align="center">· Design Review</td>
<td align="center">· 设计复审 (和同事审核设计文档)</td>
<td align="center">30</td>
<td align="center">20</td>
</tr>
<tr>
<td align="center">· Coding Standard</td>
<td align="center">· 代码规范 (为目前的开发制定合适的规范)</td>
<td align="center">30</td>
<td align="center">15</td>
</tr>
<tr>
<td align="center">· Design</td>
<td align="center">· 具体设计</td>
<td align="center">90</td>
<td align="center">120</td>
</tr>
<tr>
<td align="center">· Coding</td>
<td align="center">· 具体编码</td>
<td align="center">900</td>
<td align="center">1140</td>
</tr>
<tr>
<td align="center">· Code Review</td>
<td align="center">· 代码复审</td>
<td align="center">120</td>
<td align="center">240</td>
</tr>
<tr>
<td align="center">· Test</td>
<td align="center">· 测试（自我测试，修改代码，提交修改）</td>
<td align="center">180</td>
<td align="center">180</td>
</tr>
<tr>
<td align="center">Reporting</td>
<td align="center">报告</td>
<td align="center">210</td>
<td align="center">375</td>
</tr>
<tr>
<td align="center">· Test Report</td>
<td align="center">· 测试报告</td>
<td align="center">60</td>
<td align="center">300</td>
</tr>
<tr>
<td align="center">· Size Measurement</td>
<td align="center">· 计算工作量</td>
<td align="center">30</td>
<td align="center">15</td>
</tr>
<tr>
<td align="center">· Postmortem &amp; Process Improvement Plan</td>
<td align="center">· 事后总结, 并提出过程改进计划</td>
<td align="center">120</td>
<td align="center">60</td>
</tr>
<tr>
<td align="center"></td>
<td align="center">合计</td>
<td align="center">1800</td>
<td align="center">2280</td>
</tr>
</tbody></table>
<h2 id="二、解题思路"><a href="#二、解题思路" class="headerlink" title="二、解题思路"></a>二、解题思路</h2><h3 id="1、规则简介"><a href="#1、规则简介" class="headerlink" title="1、规则简介"></a>1、规则简介</h3><p>&ensp;&ensp;Nonograms是一种非常有趣的拼图游戏。玩家需要根据网格周围所给出的数字，在网格中选择方格进行填色或者留空，从而完成一幅图画。这样的图画在结构上可以简单，也可以复杂;在颜色上不仅可以是单种颜色的黑白块，也可以包含其它颜色。下图展示了简单和复杂游戏最终的结束情况。游戏结束后，玩家可以得到一幅漂亮的图画。</p>
<p><img src="1.png" alt="图1 单色简单的Nonograms"><br><img src="2.png" alt="图2 彩色复杂的Nonograms"></p>
<p>通过对这个游戏的简单分析，并查阅相应的资料，发现此游戏的基本游戏功能较为简单，主要难点在于问题求解算法。经查阅，此问题的求解是一个NP问题，即不存在多项式时间的求解算法。另一方面，为了方面扩展，考虑在程序编写完成后再为程序编写GUI界面，设想使用两种不同的语言实现界面和程序功能。这就涉及到跨语言的代码调用。使用C++实现程序功能，并编译生成动态链接库文件(.dll)，以供使用C#编写的GUI界面调用。因此学习动态链接库的使用也是一个难点。</p>
<h3 id="2、需求分析"><a href="#2、需求分析" class="headerlink" title="2、需求分析"></a>2、需求分析</h3><p>a.使用像素图生成各种规格的拼图至文件<br>b.读取文件内的拼图问题，求解并将结果输出到文件<br>c.为游戏生成器做一个GUI界面，并附上一个简单的使用说明（附加题）</p>
<h3 id="3、程序规划"><a href="#3、程序规划" class="headerlink" title="3、程序规划"></a>3、程序规划</h3><p>&ensp;&ensp;由于此任务主要难点在问题解决算法实现上，而本人对c\c++较为熟悉，因此使用c\c++作为算法部分编写的语言；而GUI界面部分，使用c#进行编写。将算法程序编译生成dll链接库，c#界面程序通过调用dll链接库完成整个项目界面、算法的整合。</p>
<p>&ensp;&ensp;在算法设计上，以面向对象的方式设计整个软件，并实现从像素图生成拼图文件和对拼图文件进行求解。</p>
<p>&ensp;&ensp;GUI界面设计方面，将在算法部分设计完成后再进行实现。</p>
<h2 id="三、设计实现过程"><a href="#三、设计实现过程" class="headerlink" title="三、设计实现过程"></a>三、设计实现过程</h2><p>在设计过程中，我首先进行的是对游戏基本游戏任务需求及功能的设计，而GUI的设计计划在游戏功能完成后再进行设计。</p>
<h3 id="1、基本功能设计"><a href="#1、基本功能设计" class="headerlink" title="1、基本功能设计"></a>1、基本功能设计</h3><p>根据游戏的实际特点，设计了三个类，分别为：Color、Picture、Nonograms。</p>
<img src = "3.png" width = "450" height = "450" alt="图3 类图" align=center />

<p>Color类完成对像素点颜色的描述及一些涉及到颜色操作的实现。</p>
<p>Picture类是对游戏中所涉及到的图片的描述，包括长、宽、颜色字典等内容。Color类与此类是聚合关系。在这个类中实现了从通用的BMP图片加载到Picture对象的方法，同时提供了拓展的空间，进一步可以添加更多的方法以支持其它各类图片。</p>
<p>Nonograms类是完成游戏功能的主类。Picture与此类是聚合关系和依赖关系。在这个类中实现了游戏的众多基本操作。包含多个属性和方法，提供了游戏的生成、保存、加载、求解多个方法。</p>
<h4 id="a、Color类"><a href="#a、Color类" class="headerlink" title="a、Color类"></a>a、Color类</h4><p>Color类用于描述颜色。使用R、G、B颜色系统，因此包含了r、g、b三个无符号字符型变量。定义了两个静态方法，用于衡量颜色之间的“距离”及判断颜色是否相同。对于颜色的距离，采用简单的欧氏距离来做衡量，考虑两个颜色对象的三个颜色分量之间的差之平方和，作为他们之间的距离。考虑实际游戏颜色使用过程中，对于颜色的辨识度并不高，因此判断两种颜色相同并不严格通过r、g、b三个颜色分量相同，或者说颜色间距离为0来判定。这里以一个常数值MAX_DIST来作为阈值，当颜色间距离小于此数，即认为它们为同一种颜色。</p>
<img src = "Color.png" alt="Color类" align=center />

<h4 id="b、Picture类"><a href="#b、Picture类" class="headerlink" title="b、Picture类"></a>b、Picture类</h4><p>Picture类用于描述图片。这个类在整个游戏中有两个作用：</p>
<ul>
<li>1、生成游戏时，负责从BMP等图片类型转化为游戏内部可以识别解析的数据结构</li>
<li>2、游戏进行时，负责存储游戏的尺寸、记录游戏过程中涉及到的颜色填充变化和完成其它对图片的操作</li>
</ul>
<p>这两个作用分别对应需求中游戏生成、游戏求解的两个需求。数据结构方面，此类包含三个整型变量width、height、cNum，一个N*M的整型数组mp、一个Color类型的数组dic作为颜色字典。颜色字典使得图片不仅支持黑白两种颜色的图像，还支持彩色的图片。而之所以采用颜色字典的方式对颜色进行记录有两方面的考虑：一是减小游戏问题文件的结构和大小，使得文件的读取解析更加容易；二是在问题求解中，直接使用颜色较为不便做颜色比对，且对性能可能有一定的损失，采用颜色字典使得颜色得比对简单明晰。</p>
<p>为了实现第一个作用，在类中设计了一个方法read_Bmp(src),从路径中读取一幅BMP图片，转化为上述的数据结构格式。详细的图片载入方法见：<a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90">程序设计——拼图文件生成</a></p>
<p>而对第二个作用，通过print()方法来完成游戏照片的打印输出。这里提供了两个重载，以供命令台打印输出或输出保存到文件。</p>
<img src = "Picture.png" alt="Picture类" align=center />


<h4 id="c、Nonograms类"><a href="#c、Nonograms类" class="headerlink" title="c、Nonograms类"></a>c、Nonograms类</h4><p>此类是整个游戏对外提供服务的类。上面两个类均在此类中进行调用及使用。数据结构方面，由于此类涉及到用户层面的接触及操作，因此对于属性、方法的权限切割较详细，从而提供一定的数据独立性与程序的数据保护。Pictrue对象pic用于记录游戏的基本参数(如游戏规模、颜色字典等)和游戏过程中涉及到的像素点取值变化。四个int型数组用于记录游戏的问题，包括左侧、上侧的颜色块的连续块数字、对应块的颜色标号。同时在私有变量中也存储了一组这样的游戏问题矩阵，这是供求解函数所使用的数据。由于数组过大，放在程序实现体中会导致堆栈占用过大警告，因此在此处声明。</p>
<p>对游戏的生成，在generate(Picture pic)方法进行实现。此方法以一个图片作为输入，通过扫描这个图片中的内容，即可完成游戏的生成。具体游戏生成的代码、设计细节见：<a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90">程序设计——拼图文件生成</a></p>
<p>对游戏的保存和加载，在save(string dest)、load(string src)两个方法进行实现。这个方法负责打开从路径指定的一个文件，写入生成的游戏问题或从文件读取相应的游戏问题到Nonograms对象。游戏问题文件的数据结构和解析方式在这两个方法中是恰好相对应的。生成的游戏问题文件推荐以.txt形式进行存储，从而可以在游戏外对游戏问题文件进行阅读和修改等。</p>
<p>对游戏的求解，通过solve()方法进行实现。求解的结果直接存储在pic对象(Picture的实例)中。这个方法仅是一个接口，具体的算法在私有方法dfs()中进行实现，通过深度优先搜索的方式进行求解。check()方法用于检查dfs所推断出的图片是否符合题目要求。求解算法的详细设计详细见：<a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a></p>
<img src = "Nonograms.png" alt="Nonograms类" align=center />

<h3 id="2、GUI界面设计"><a href="#2、GUI界面设计" class="headerlink" title="2、GUI界面设计"></a>2、GUI界面设计</h3><p>使用C#涉及GUI界面。</p>
<p>GUI界面中需要调用之前使用C++编译生成的动态链接库文件，Nonograms.dll。通过调用dll中提供的相关类及方法，完成游戏功能的实现。因此，GUI部分仅提供一个对外进行操作的接口。根据需求，设计将界面划分为两大区域：左侧进行游戏图像的显示，由上下两部分构成，分别显示图像区域和颜色选择区域；右侧提供对游戏的管理功能，并添加系列功能按钮，及文件路径读取框等。</p>
<p><img src="14.png" alt="UI界面简图"></p>
<p>在界面设计中，以按钮作为每一个像素，通过设置按钮的响应函数、颜色、文本等信息，来完成题目的显示、颜色的选择、游戏像素颜色的改变。</p>
<p>通过update_GUI()函数完成左侧界面中所有按钮对象的添加与更新。在窗口创建及每一次载入新的游戏时，调用它完成按钮更新。界面展示见：<a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94GUI/">运行展示——GUI</a></p>
<p><img src="15.png" alt="UI界面"></p>
<h3 id="3、单元测试设计"><a href="#3、单元测试设计" class="headerlink" title="3、单元测试设计"></a>3、单元测试设计</h3><p>由于本软件以面向对象的方式进行设计和实现，因此单元测试也计划以类进行。</p>
<h5 id="a、Color类的测试"><a href="#a、Color类的测试" class="headerlink" title="a、Color类的测试"></a>a、Color类的测试</h5><p>Color类用于描述颜色，是一个r、g、b三个8位的数值变量。由于Color类的功能较为简单，且仅涉及数值操作，因此针对它的两个静态方法，使用<strong>等价类法</strong>设计测试用例。</p>
<p>测试用例：</p>
<ol>
<li><p>两个非法颜色</p>
<p> 输入：Color1(-1,-2,-3) Color2(-4,-5,-6)</p>
<p> 输出：提示报错</p>
</li>
<li><p>一个非法颜色、一个合法颜色</p>
<p> 输入：Color1(4,5,6) Color2(-4,-5,-6)</p>
<p> 输出：提示报错</p>
</li>
<li><p>两个合法颜色  判定同种颜色</p>
<p> 输入：Color1(1,2,3) Color2(4,5,6)</p>
<p> 输出：dist = 1.732 same = True</p>
</li>
<li><p>两个合法颜色  判定不同种颜色</p>
<p> 输入：Color1(1,2,3) Color2(100,150,200)</p>
<p> 输出：dist = 17032.670 same = False</p>
</li>
</ol>
<h5 id="b、Picture类的测试"><a href="#b、Picture类的测试" class="headerlink" title="b、Picture类的测试"></a>b、Picture类的测试</h5><p>Picture类是游戏内所使用的描述图像的类。它存储了游戏图片的基本颜色、图像数据等。这里主要涉及到对三个方法的测试。对于图像读取方法read_BMP()，由于其中涉及到较多的系统库函数，因此使用<strong>黑盒</strong>测试模型。考虑图片的大小是对Picture类影响的关键，这里确定使用<strong>边界值法</strong>涉及测试用例。</p>
<p>边界值：width=1，heigth=1‘；width=128，height=128</p>
<p>测试用例：</p>
<ol>
<li><p>输入：大小位1*1的图片</p>
<p>输出：正常读取、输出、保存图片</p>
</li>
<li><p>输入：大小位127*127的图片</p>
<p> 输出：正常读取、输出、保存图片</p>
</li>
<li><p>输入：大小位128*128的图片</p>
<p> 输出：正常读取、输出、保存图片</p>
</li>
<li><p>输入：大小位129*129的图片</p>
<p> 输出：提示报错，”This picture(129*129) is too big.”</p>
</li>
<li><p>输入：路径不存在图片</p>
<p> 输出：提示报错，”Can not openfile: …”</p>
</li>
</ol>
<h5 id="c、Nonograms类的测试"><a href="#c、Nonograms类的测试" class="headerlink" title="c、Nonograms类的测试"></a>c、Nonograms类的测试</h5><p>Nonograms是整合游戏所有功能类，因此对于Nonograms的单元测试，实际也就是对整个游戏程序的集成测试。因此，对于该类的每一个方法，均涉及单独的方法进行单元测试。由于涉及到的用例内容较多，下面只给出针对各个方法测试所选用的测试方法和测试用例设计思路。</p>
<ol>
<li><p>generate(Picture pic)</p>
<p> 本方法完成对拼图游戏的生成。从白盒测试的角度看，此方法内只涉及到简单的循环、判断操作，因此使用<strong>路径测试</strong>的方式进行测试。这里的判定主要是对于单色图片、彩色图片、颜色块的连续情况而进行。通过绘制程序的执行流图，设计适合的测试图片，仅使用一张合适的图片即可完成对此方法的测试。</p>
</li>
<li><p>save(std::string dest)</p>
<p> 本方法完成对生成的图片问题的保存。考虑程序内主要涉及到文件操作，因此使用<strong>判定覆盖</strong>的方式，针对保存路径存在与否设计测试用例。针对程序内的循环部分，则以<strong>边界值法</strong>的方式，针对不同大小规模的问题进行测试。</p>
</li>
<li><p>load(std::string src)</p>
<p> 本方法完成对已经生成的问题的加载。由于save、load函数完成的功能相互耦合，因此对此方法的测试可以同save()方法的测试<strong>结合进行</strong>。对问题路径存在与否、不同大小规模的问题进行测试。</p>
</li>
<li><p>print()</p>
<p> 本方法完成对已经求解的问题结果进行保存。这个方法有两个重载，无输入的方法将求解结果打印至终端，以路径字符串为输入的方法将结果保存至相应路径。两个重载在实现上基本相同，仅有是否涉及文件操作的差别。对于基本功能，使用<strong>边界值法</strong>的方式针对不同大小规模的问题进行测试。针对输出至文件的重载，增加<strong>判定覆盖</strong>的测试用例，对打开文件失败的用例情况增加测试用例。</p>
</li>
</ol>
<h2 id="四、性能分析"><a href="#四、性能分析" class="headerlink" title="四、性能分析"></a>四、性能分析</h2><p>程序的性能分析，按游戏程序的功能特征，分为三部分进行：</p>
<ul>
<li>游戏生成</li>
<li>游戏保存</li>
<li>游戏求解</li>
</ul>
<h3 id="1、游戏生成"><a href="#1、游戏生成" class="headerlink" title="1、游戏生成"></a>1、游戏生成</h3><p>按照最大支持图片尺寸为128*128的标准，使用一张随意绘制的图片作为源图片。对此图片执行1000次重复的游戏生成，并查看其用时。</p>
<p><img src="4.bmp" alt="测试用例图片"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	Nonograms game;</span><br><span class="line">	Picture pic;</span><br><span class="line">	<span class="built_in">string</span> src = <span class="string">&quot;C:/Users/王欣哲/Desktop/codes/软件工程/Big_1.bmp&quot;</span>;</span><br><span class="line">	<span class="built_in">string</span> dest = <span class="string">&quot;C:/Users/王欣哲/Desktop/codes/软件工程/Big_1.txt&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">1000</span>; i++) &#123;</span><br><span class="line">		pic.read_BMP(src);</span><br><span class="line">		game.generate(pic);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>使用Visual Studio 2019所提供的性能探查器，生成性能测试报告。从报告中可以看到，在1000次生成中，程序使用的时间为9.568s，即平均生成一个问题耗时9.568ms。在这样的情况下，生成一个最复杂的问题的时间也是很少的。</p>
<img src = "5.png" alt="程序性能报告" align=center />

<p>上图是程序运行中，IO、内核、文件系统、图形四种任务运行所占时间饼状图。从图中可以看到，程序约80%的时间均运行于IO任务，因此可以推断，程序主要运行时间均花费在图片的读取上。进一步分析软件执行过程中各个函数模块占用CPU的时间，可以看到，read_BMP()函数占用了97.8%的CPU时间。</p>
<p><img src="6.png" alt="CPU使用率"></p>
<p>这个函数正是执行图片读取的函数。进一步探查此函数的内部，有56.79%的CPU时间消耗在外部代码中。经过综合对比分析，此部分代码所执行的操作为对BMP图片的读取操作；而另有39.53%的CPU时间消耗在查询颜色字典的操作中。对于第一部分的优化，可以考虑使用双缓存的机制，使IO操作和图片像素解析同步进行。对于第二部分的优化，则可以按照颜色的碰撞频率构建优先队列，以使得碰撞检测的时间降低。针对此处的优化设计算法实现均较为复杂，考虑到目前此处并未遇到性能问题，对复杂图像的生成时间复杂度也较低，因此不考虑做进一步优化。</p>
<img src = "7.png" width = "700" alt="read_BMP()函数内部语句消耗CPU时间图" align=center />

<h3 id="2、游戏保存"><a href="#2、游戏保存" class="headerlink" title="2、游戏保存"></a>2、游戏保存</h3><p>同样对游戏支持的最大尺寸128*128尺寸的问题作为标准，执行游戏1000次游戏的保存，并检测整个过程的性能。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	Nonograms game;</span><br><span class="line">	Picture pic;</span><br><span class="line">	<span class="built_in">string</span> src = <span class="string">&quot;C:/Users/王欣哲/Desktop/codes/软件工程/Big_1.bmp&quot;</span>;</span><br><span class="line">	<span class="built_in">string</span> dest = <span class="string">&quot;C:/Users/王欣哲/Desktop/codes/软件工程/Big_1.txt&quot;</span>;</span><br><span class="line">	pic.read_BMP(src);</span><br><span class="line">	game.generate(pic);</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">1000</span>; i++) &#123;</span><br><span class="line">		game.save(dest);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>同样使用Visual Studio的性能探查器，生成性能测试报告。从时间上来看，整个过程耗时26.604s，平均一次保存耗时26.604ms，因此一次游戏保存消耗的时间也是很小的。从占用文件大小上来看，生成的游戏文件大小为100K，也是很小的且可以接受的。相较于源BMP文件大小为52KB，增加一倍大小换来读取、处理的方便性是值得的。从下图中可以看到，游戏保存任务中，CPU所涉及到的绝大多数操作仍为IO操作。</p>
<img src = "8.png" alt="程序性能报告" align=center />

<p>进一步探查save函数内部执行情况，95.39%的CPU时间均花费于fprintf语句。这说明程序的绝大多数时间均花费在文件操作上。对于这一部分的进一步优化，目前没有进一步优化的算法。而考虑性能方面，目前的保存时间也是可以接受的，因此不考虑做进一步优化。</p>
<img src = "9.png" alt="函数内部语句消耗CPU时间图" align=center />


<h3 id="3、游戏求解"><a href="#3、游戏求解" class="headerlink" title="3、游戏求解"></a>3、游戏求解</h3><p>下面以黑白图片作为性能测试用例，生成相应的游戏问题文件，并进行游戏求解的性能测试。</p>
<img src = "10.bmp" width = 150 alt="5*5 黑白测试图片" align=center />

<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	Nonograms game;</span><br><span class="line">	<span class="built_in">string</span> src = <span class="string">&quot;C:/Users/王欣哲/Desktop/codes/软件工程/1.bmp&quot;</span>;</span><br><span class="line"></span><br><span class="line">	game.generate(src);</span><br><span class="line">	</span><br><span class="line">	game.solve();</span><br><span class="line"></span><br><span class="line">	game.print();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>使用Visual Studio提供的性能探查器生成测试报告。对于整个规模5*5的问题，整个求解过程耗时10.396s，因此求解所消耗的时间是较大的。下图展示生成的测试报告。</p>
<img src = "11.png" alt="程序性能报告" align=center />

<img src = "12.png" alt="函数内部语句消耗CPU时间图" align=center />

<p>从报告中可以看到，求解程序的大部分时间均花费在check()方法上。由于这个方法负责检测当前棋局是否符合题目要求，因此被频繁调用是正常的。进一步查看此函数内部执行情况，87.58%的代码均执行了memset()函数。经过对函数执行结构的分析，此处反复执行的memset函数完全可以移除。经过优化，程序的求解性能得到了一定的提升。</p>
<img src = "13.png" alt="程序性能报告" align=center />

<p>函数的执行时间从10.396s缩减为3.387s，有约3倍的性能提升。此时的性能已基本满足我们对小规模游戏问题快速求解的性能要求，在非正式的测试中，对于稍复杂、稍大规模问题的求解，也可以在较短的时间内完成。因此采用现在的求解算法作为最终算法。进一步改进方面，可以对深度优先搜索算法的搜索方式进行优化，使用更加复杂的方式对问题颜色块按组生成排列进行搜索。这样对于更大规模的问题，也可以有更好的求解表现。同时对check()方法，也可以在每行的像素检测完成后，即安排与问题矩阵的对比，从而尽早判断当前生成解是否正确，减少判断时间。</p>
<h2 id="五、代码说明"><a href="#五、代码说明" class="headerlink" title="五、代码说明"></a>五、代码说明</h2><p>重要函数的代码实现说明在：<a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90">程序设计——拼图文件生成</a>、<a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a>两篇文章中进行了详细说明。这里对框架代码进行详细说明。</p>
<h3 id="1-主程序"><a href="#1-主程序" class="headerlink" title="1.主程序"></a>1.主程序</h3><p>主程序部分代码提供了用户进行游戏的界面窗口。通过命令，用户可以完成游戏的新建、保存、加载、求解、保存功能。在完成基本的初始化后，程序进入一个游戏的死循环，直至用户输入终止命令。game对象是实例的游戏，所有的游戏操作均通过调用此类的方法实现。主程序的其它代码均为功能性支撑代码。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;-----------------------\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;                       \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;        拼图游戏        \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;                       \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;         王欣哲         \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;       1120182955      \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;                       \n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;-----------------------\n\n&quot;</span>);</span><br><span class="line"></span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;new path       Create a new problem\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;save path      Save the problem\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;load path      Load a problem\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;solve          Solve a problem\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;print (path)   print the result\n&quot;</span>);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;exit           exit the game\n&quot;</span>);</span><br><span class="line"></span><br><span class="line">	Nonograms game;</span><br><span class="line">	<span class="keyword">char</span> str[<span class="number">1005</span>];</span><br><span class="line">	<span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;&gt;&gt;&quot;</span>);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">		<span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;new&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">			game.generate(str);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;save&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">			game.save(<span class="built_in">string</span>(str));</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;load&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">			game.load(<span class="built_in">string</span>(str));</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;solve&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="keyword">if</span> (game.solve()) &#123;</span><br><span class="line">				<span class="built_in">printf</span>(<span class="string">&quot;Finish!\n&quot;</span>);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="built_in">printf</span>(<span class="string">&quot;Can&#x27;t be solved\n&quot;</span>);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;print&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="keyword">if</span> (getchar() == <span class="string">&#x27; &#x27;</span>) &#123;</span><br><span class="line">				<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">				game.print(<span class="built_in">string</span>(str));</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				game.print();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (<span class="built_in">strcmp</span>(str, <span class="string">&quot;exit&quot;</span>) == <span class="number">0</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-动态链接库编译"><a href="#2-动态链接库编译" class="headerlink" title="2.动态链接库编译"></a>2.动态链接库编译</h3><p>动态链接库可以使别的编程语言能够调用已经编写好的C++程序，起到提高内聚程度、降低模块间耦合度、。因此，为了使GUI界面与程序实现相独立，同时提高一定的性能，在设计时已确定使用C++实现游戏功能代码，使用C#实现游戏GUI界面。通过Visual Studio中提供的编译配置，设置输出为**动态链接库(.dll)**，编译生成项目即可得到相应的动态链接库。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;Picture.h&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;Nonograms.h&quot;</span></span></span><br></pre></td></tr></table></figure>
<h3 id="3-Color类"><a href="#3-Color类" class="headerlink" title="3.Color类"></a>3.Color类</h3><p>Color类完成对颜色的描述。下面展示Color类的头文件。其中包含r、g、b三个变量用于描述RGB颜色的三个分量数值。WHITE、BLACK两个为定义的静态常量，说明两个系统定义好的颜色。包含两个方法，完成对颜色的比较及相同颜色判定。实现方法的代码说明详细见<a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90">程序设计——拼图文件生成</a>。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Color</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">static</span> Color WHITE;</span><br><span class="line">	<span class="keyword">const</span> <span class="keyword">static</span> Color BLACK;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">char</span> r = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">char</span> g = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">unsigned</span> <span class="keyword">char</span> b = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	Color();</span><br><span class="line">	Color(<span class="keyword">int</span> r, <span class="keyword">int</span> g, <span class="keyword">int</span> b);</span><br><span class="line"></span><br><span class="line">	<span class="comment">//颜色的距离 欧氏距离</span></span><br><span class="line">	<span class="function"><span class="keyword">static</span> <span class="keyword">float</span> <span class="title">dist</span><span class="params">(<span class="keyword">const</span> Color&amp; a, <span class="keyword">const</span> Color&amp; b)</span></span>;</span><br><span class="line">	<span class="comment">//颜色相同 基于颜色距离</span></span><br><span class="line">	<span class="function"><span class="keyword">static</span> <span class="keyword">bool</span> <span class="title">same</span><span class="params">(<span class="keyword">const</span> Color&amp; a, <span class="keyword">const</span> Color&amp; b)</span></span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="4-Picture类"><a href="#4-Picture类" class="headerlink" title="4.Picture类"></a>4.Picture类</h3><p>Picture类描述游戏中涉及到的图片。包含一些变量，用于描述图片的数据及属性。图片的保存通过颜色字典，实现图像大小的压缩显示，即dic[MAX_COLOR]一变量是设计的颜色字典。包含三个方法，read_BMP()方法完成从BMP位图加载图片的功能；两个print方法完成图片到命令台和到文件的打印输出功能。这样的设计方式使得程序能够根据需求，进一步扩展以支持对其它格式图片的读取。具体方法的详细代码说明见<a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90">程序设计——拼图文件生成</a>。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Picture</span>&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="keyword">int</span> width;				<span class="comment">//宽</span></span><br><span class="line">	<span class="keyword">int</span> height;				<span class="comment">//高</span></span><br><span class="line">	<span class="keyword">int</span> cNum;				<span class="comment">//颜色数</span></span><br><span class="line">	<span class="keyword">int</span> mp[N][M] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//颜色地图 N*M</span></span><br><span class="line">	Color dic[MAX_COLOR];	<span class="comment">//颜色字典 MAX_COLOR</span></span><br><span class="line">	 </span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="comment">//读取BMP图片</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">read_BMP</span><span class="params">(<span class="built_in">std</span>::<span class="built_in">string</span> src)</span></span>;</span><br><span class="line">	<span class="comment">//打印输出图片</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(<span class="built_in">std</span>::<span class="built_in">string</span> src)</span></span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="5-Nonograms类"><a href="#5-Nonograms类" class="headerlink" title="5.Nonograms类"></a>5.Nonograms类</h3><p>Nonograms类是游戏的主类，所有的游戏功能均同通过本类进行实现。本类中对变量、方法进行了详细的访问权限划分，公有变量存储游戏的主信息，私有变量为工作变量，供部分方法运行时使用。这里包含五个公有方法，提供了游戏的所有对外功能接口，具体功能在下面的头文件代码中进行详细说明。私有方法有两个，它们都是为求解游戏而提供的方法。具体详细代码说明见<a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a>。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Nonograms</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	Picture pic;	<span class="comment">//图像</span></span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> a[N][M / <span class="number">2</span>] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//左侧矩阵</span></span><br><span class="line">	<span class="keyword">int</span> ac[N][M / <span class="number">2</span>] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//左侧颜色</span></span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> b[N / <span class="number">2</span>][M] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//右侧矩阵</span></span><br><span class="line">	<span class="keyword">int</span> bc[N / <span class="number">2</span>][M] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//右侧矩阵</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="comment">//求解拼图游戏</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">solve</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//从图像生成拼图游戏</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">generate</span><span class="params">(Picture pic)</span></span>;</span><br><span class="line">	<span class="comment">//保存拼图游戏文件</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">save</span><span class="params">(<span class="built_in">std</span>::<span class="built_in">string</span> dest)</span></span>;</span><br><span class="line">	<span class="comment">//从文件加载拼图</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">load</span><span class="params">(<span class="built_in">std</span>::<span class="built_in">string</span> src)</span></span>;</span><br><span class="line">	<span class="comment">//打印输出求解后图像</span></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	<span class="keyword">int</span> at[N][M / <span class="number">2</span>] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//左侧矩阵</span></span><br><span class="line">	<span class="keyword">int</span> atc[N][M / <span class="number">2</span>] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//左侧颜色</span></span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> bt[N / <span class="number">2</span>][M] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//右侧矩阵</span></span><br><span class="line">	<span class="keyword">int</span> btc[N / <span class="number">2</span>][M] = &#123; <span class="number">0</span> &#125;;	<span class="comment">//右侧矩阵</span></span><br><span class="line">	<span class="comment">//检查图片是否与题目符合</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">	<span class="comment">//深搜求解</span></span><br><span class="line">	<span class="function"><span class="keyword">bool</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span></span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="6-GUI"><a href="#6-GUI" class="headerlink" title="6.GUI"></a>6.GUI</h3><p>目前仅实现了GUI界面的基本显示功能。这里主要对update_GUI()函数进行说明。</p>
<p>此函数以游戏的规模width、height作为输入，通过解析动态链接库中所提供的Nonograms对象中的各参数，完成对游戏内容的写入。_x、_y为左侧和上侧问题显示板的大小规模，x、y为按钮对象在框体中的显示位置。通过一个双层大循环遍历所有的按钮位置，并根据此按钮的位置，确定此按钮的功能，并选择相应的方式对按钮进行着色等处理。</p>
<figure class="highlight c#"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">update_GUI</span>(<span class="params"><span class="built_in">int</span> width, <span class="built_in">int</span> height</span>)</span></span><br><span class="line"><span class="function"></span>        &#123;</span><br><span class="line">            <span class="built_in">int</span> x = <span class="number">35</span>, y = <span class="number">35</span>;</span><br><span class="line">            <span class="built_in">int</span> _x = Convert.ToInt32(Math.Ceiling(Convert.ToDouble(height) / <span class="number">2</span>));</span><br><span class="line">            <span class="built_in">int</span> _y = Convert.ToInt32(Math.Ceiling(Convert.ToDouble(width) / <span class="number">2</span>));</span><br><span class="line">            Button b;</span><br><span class="line">            <span class="keyword">for</span> (<span class="built_in">int</span> i = <span class="number">0</span>; i &lt; height + _x; i++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="built_in">int</span> j = <span class="number">0</span>; j &lt; width + _y; j++)</span><br><span class="line">                &#123;</span><br><span class="line">                    x = <span class="number">100</span> + <span class="number">21</span> * i;</span><br><span class="line">                    y = <span class="number">20</span> + <span class="number">21</span> * j;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">                    <span class="keyword">if</span> (i &lt; _x &amp;&amp; j &lt; _y)</span><br><span class="line">                    &#123;</span><br><span class="line">                        <span class="keyword">continue</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (i &gt;= _x &amp;&amp; j &lt; _y)</span><br><span class="line">                    &#123;</span><br><span class="line">                        <span class="comment">//左侧</span></span><br><span class="line">                        b = <span class="keyword">new</span> Button();</span><br><span class="line">                        b.Width = <span class="number">20</span>;   <span class="comment">//宽</span></span><br><span class="line">                        b.Height = <span class="number">20</span>;  <span class="comment">//高</span></span><br><span class="line">                        b.BackColor = Color.PaleGoldenrod;<span class="comment">//颜色</span></span><br><span class="line">                        b.Text = <span class="string">&quot;0&quot;</span>;</span><br><span class="line">                        b.Location = <span class="keyword">new</span> Point(x, y);</span><br><span class="line">                        panel4.Controls.Add(b);</span><br><span class="line"></span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (i &lt; _x &amp;&amp; j &gt;= _y)</span><br><span class="line">                    &#123;</span><br><span class="line">                        <span class="comment">//上侧</span></span><br><span class="line">                        b = <span class="keyword">new</span> Button();</span><br><span class="line">                        b.Width = <span class="number">20</span>;   <span class="comment">//宽</span></span><br><span class="line">                        b.Height = <span class="number">20</span>;  <span class="comment">//高</span></span><br><span class="line">                        b.BackColor = Color.Beige;<span class="comment">//颜色</span></span><br><span class="line">                        b.Text = <span class="string">&quot;0&quot;</span>;</span><br><span class="line">                        b.Location = <span class="keyword">new</span> Point(x, y);</span><br><span class="line">                        panel4.Controls.Add(b);</span><br><span class="line"></span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (i &gt;= _x &amp;&amp; j &gt;= _y)</span><br><span class="line">                    &#123;</span><br><span class="line">                        <span class="comment">//主界面</span></span><br><span class="line">                        b = <span class="keyword">new</span> Button();</span><br><span class="line">                        b.Width = <span class="number">20</span>;   <span class="comment">//宽</span></span><br><span class="line">                        b.Height = <span class="number">20</span>;  <span class="comment">//高</span></span><br><span class="line">                        b.BackColor = Color.White;<span class="comment">//颜色</span></span><br><span class="line">                        b.Location = <span class="keyword">new</span> Point(x, y);</span><br><span class="line">                        panel4.Controls.Add(b);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            b = <span class="keyword">new</span> Button();</span><br><span class="line">            b.Width = <span class="number">30</span>;</span><br><span class="line">            b.Height = <span class="number">30</span>;</span><br><span class="line">            b.BackColor = Color.White;</span><br><span class="line">            b.Location = <span class="keyword">new</span> Point(<span class="number">220</span>, <span class="number">25</span>);</span><br><span class="line">            panel3.Controls.Add(b);</span><br><span class="line"></span><br><span class="line">            b = <span class="keyword">new</span> Button();</span><br><span class="line">            b.Width = <span class="number">30</span>;</span><br><span class="line">            b.Height = <span class="number">30</span>;</span><br><span class="line">            b.BackColor = Color.Black;</span><br><span class="line">            b.Location = <span class="keyword">new</span> Point(<span class="number">350</span>, <span class="number">25</span>);</span><br><span class="line">            panel3.Controls.Add(b);</span><br><span class="line">        &#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="http://bit-wxz.gitee.io/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/" data-id="ckkva2tfb0005nsmsddk55ugu" data-title="拼图游戏——综述" class="article-share-link">分享</a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">前一篇</strong>
      <div class="article-nav-title">
        
          程序设计——拼图文件生成
        
      </div>
    </a>
  
  
    <a href="/hexo/2020/12/26/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E6%B8%B8%E6%88%8F%E4%BB%8B%E7%BB%8D/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">后一篇</strong>
      <div class="article-nav-title">拼图游戏——游戏介绍</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">归档</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2021/02/">二月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2021/01/">一月 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/hexo/archives/2020/12/">十二月 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94GUI/">运行展示——GUI</a>
          </li>
        
          <li>
            <a href="/hexo/2021/02/07/%E8%BF%90%E8%A1%8C%E5%B1%95%E7%A4%BA%E2%80%94%E2%80%94%E5%91%BD%E4%BB%A4%E5%8F%B0/">运行展示——命令台</a>
          </li>
        
          <li>
            <a href="/hexo/2021/02/03/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3/">程序设计——问题求解</a>
          </li>
        
          <li>
            <a href="/hexo/2021/01/25/%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E2%80%94%E2%80%94%E6%8B%BC%E5%9B%BE%E6%96%87%E4%BB%B6%E7%94%9F%E6%88%90/">程序设计——拼图文件生成</a>
          </li>
        
          <li>
            <a href="/hexo/2020/12/28/%E6%8B%BC%E5%9B%BE%E6%B8%B8%E6%88%8F%E2%80%94%E2%80%94%E7%BB%BC%E8%BF%B0/">拼图游戏——综述</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2021 王欣哲 1120182955<br>
	  
	  
	   
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/hexo/" class="mobile-nav-link">Home</a>
  
</nav>
    


<script src="/hexo/js/jquery-3.4.1.min.js"></script>



  
<script src="/hexo/fancybox/jquery.fancybox.min.js"></script>




<script src="/hexo/js/script.js"></script>





  </div>
</body>
</html>